import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class Demo1 {


    //LCR 120. 寻找文件副本
    public int findRepeatDocument(int[] documents) {
        int n = documents.length;
        int[] hash = new int[n];
        for(int x : documents) {
            if(++hash[x] > 1) return x;
        }
        return 0;
    }


    //240. 搜索二维矩阵 II
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int i = m - 1, j = 0;
        while(i >= 0 && j < n) {
            if(matrix[i][j] == target) return true;
            else if(matrix[i][j] > target) i--;
            else j++;
        }
        return false;
    }


    //LCR 122. 路径加密
    public String pathEncryption(String path) {
        StringBuilder ret = new StringBuilder();
        for(char ch : path.toCharArray()) {
            if(ch == '.') ret.append(' ');
            else ret.append(ch);
        }
        return ret.toString();
    }


    //LCR 123. 图书整理 I
    int[] ret;
    int count;  // 记录链表结点个数
    public int[] reverseBookList(ListNode head) {
        dfs(head, 1);
        return ret;
    }
    private void dfs(ListNode head, int pos) {
        if(head == null) {
            ret = new int[count];
            return;
        }
        count++;
        dfs(head.next, pos + 1);
        ret[count - pos] = head.val;
    }


    //LCR 124. 推理二叉树
    int pos = 0;
    Map<Integer, Integer> hash = new HashMap<>();
    public TreeNode deduceTree(int[] preorder, int[] inorder) {
        for(int i = 0; i < inorder.length; i++) hash.put(inorder[i], i);
        return constructTree(preorder, inorder, 0, inorder.length - 1);
    }
    private TreeNode constructTree(int[] preorder, int[] inorder, int left, int right) {
        if(left > right) return null;
        TreeNode root = new TreeNode(preorder[pos++]);
        // 寻找当前树的根结点在中序遍历的下标
        int index = hash.get(root.val);
        root.left = constructTree(preorder, inorder, left, index - 1);
        root.right = constructTree(preorder, inorder, index + 1, right);
        return root;
    }



    //232. 用栈实现队列
    class MyQueue {
        Stack<Integer> s1;
        Stack<Integer> s2;
        public MyQueue() {
            s1 = new Stack<>();
            s2 = new Stack<>();
        }

        public void push(int x) {
            s1.push(x);
        }

        public int pop() {
            if(s2.empty()) {
                while(!s1.empty()) {
                    s2.push(s1.pop());
                }
            }
            return s2.pop();
        }

        public int peek() {
            if(s2.empty()) {
                while(!s1.empty()) {
                    s2.push(s1.pop());
                }
            }
            return s2.peek();
        }

        public boolean empty() {
            return s1.empty() && s2.empty();
        }
    }



    //509. 斐波那契数
    public int fib(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;
        int a = 0, b = 1, c = 0;
        for(int i = 2; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }



    //153. 寻找旋转排序数组中的最小值
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        int mid, n = right;
        while(left < right) {
            mid = left + (right - left) / 2;
            if(nums[mid] > nums[n]) left = mid + 1;
            else right = mid;
        }
        return nums[left];
    }


    //154. 寻找旋转排序数组中的最小值 II
    public int findMin2(int[] nums) {
        int left = 0, right = nums.length - 1, mid;
        while(left < right) {
            mid = left + (right - left) / 2;
            if(nums[mid] < nums[right]) right = mid;
            else if(nums[mid] > nums[right]) left = mid + 1;
            else right--;
        }
        return nums[left];
    }



    //79. 单词搜索
    int row, col;
    boolean[][] vis;
    int[] dx = new int[]{0,0,1,-1};
    int[] dy = new int[]{1,-1,0,0};

    public boolean exist(char[][] board, String _word) {
        row = board.length;
        col = board[0].length;
        vis = new boolean[row][col];
        char[] word = _word.toCharArray();

        for(int i = 0; i < row; i++)
            for(int j = 0; j < col; j++) {
                if(board[i][j] == word[0]) {
                    if(dfs(board, i, j, word, 0)) return true;
                }
            }
        return false;
    }

    private boolean dfs(char[][] board, int i, int j, char[] word, int pos) {
        vis[i][j] = true;
        pos++;
        if(pos == word.length) return true;

        for(int k = 0; k < 4; k++) {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < row && y >= 0 && y < col && !vis[x][y] && board[x][y] == word[pos]) {
                if(dfs(board, x, y, word, pos)) return true;
            }
        }
        vis[i][j] = false;
        return false;
    }



    //191. 位1的个数
    public int hammingWeight(int n) {
        int ret = 0;
        while(n != 0) {
            ret++;
            n &= (n - 1);
        }
        return ret;
    }

    //338. 比特位计数
    public int[] countBits(int n) {
        int[] ret = new int[n + 1];
        for(int i = 0; i <= n; i++) {
            int count = 0;
            for(int j = i; j > 0; count++) j &= (j - 1);
            ret[i] = count;
        }
        return ret;
    }


    //LCR 134. Pow(x, n)
    public double myPow(double x, int n) {
        double ret = pow(x, Math.abs(n));
        return n < 0 ? 1.0 / ret : ret;
    }
    public double pow(double x, int n) {
        if(n == 0) return 1;
        double child = pow(x, n / 2);
        return child * child * (n % 2 == 0 ? 1.0 : x);
    }


    //LCR 136. 删除链表的节点
    public ListNode deleteNode(ListNode head, int val) {
        ListNode newHead = new ListNode(-1);
        newHead.next = head;
        ListNode prev = newHead;
        while(head.val != val) {
            prev = head;
            head = head.next;
        }
        prev.next = head.next;
        return newHead.next;
    }


    //203. 移除链表元素
    public ListNode removeElements(ListNode head, int val) {
        ListNode newHead = new ListNode();
        newHead.next = head;
        ListNode t = newHead;
        while(head != null) {
            while(head != null && head.val == val) {
                head = head.next;
            }
            t.next = head;
            t = head;
            if(head != null) head = head.next;
        }
        return newHead.next;
    }



    //10. 正则表达式匹配
    public boolean isMatch(String ss, String pp) {
        // dp[i][j]: 在字符串p 0 ~ j 区间的子串能否匹配 字符串s的 0 ~ i区间的子串
        int m = ss.length(), n = pp.length();
        ss = " " + ss; pp = " " + pp;
        char[] s = ss.toCharArray(); char[] p = pp.toCharArray();

        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for(int j = 2; j <= n; j += 2) {
            if(p[j] == '*') dp[0][j] = true;
            else break;
        }

        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(p[j] == '*') dp[i][j] = dp[i][j - 2] || (p[j - 1] == '.' || p[j - 1] == s[i]) && dp[i -1][j];
                else  dp[i][j] = (p[j] == '.' || p[j] == s[i]) && dp[i - 1][j  - 1];
            }
        }
        return dp[m][n];
    }
}
